// 文件名：exercise\lc94_姓名(演示).cpp
// 提交链接：/submissions/501466845/
// 94. 二叉树的中序遍历 - 简单题，二叉树基础训练
// 完成日期：2024/2/10
// c++, 使用栈模拟递归，可作为代码模板
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        TreeNode *cur = root;
        while (cur != nullptr || !stk.empty()) {
            if (cur == nullptr) {
                cur = stk.top(); stk.pop();
                ans.push_back(cur->val); 
                cur = cur->right;
            } else {
                stk.push(cur);
                cur = cur->left;
            }
        }
        return move(ans);
    }
};